The present invention relates to the self-tiling process of finding Iterated Function Systems (IFS) for modeling natural objects, and more particularly to an electro-optical system for performing the self-tiling process in order to find an optimal IFS for modeling a given object.
An affine transformation is a mathematical transformation equivalent to a rotation, translation, and contraction/expansion with respect to a fixed origin and coordinate system. In computer graphics, affine transformation can be used to generate fractal objects which have significant potential for modelling natural objects, such as trees, mountains and the like.
The Collage Theorem allows one to encode an image as an IFS. See, M. F. Barnsley et al., "Solution of an Inverse Problem for Fractals and Other Sets," available from the School of Mathematics, Georgia Institute of Technology, Atlanta, Ga. 30332. An IFS is a set of j mappings (M.sub.1, M.sub.2, . . . M.sub.j), each representing a particular affine transformation, that have a corresponding set of j probabilities (P.sub.1, P.sub.2, . . . P.sub.j). The j probabilities can be thought of as weighting factors for each of the corresponding j mappings or transformations. See, e.g., L. Demko et al., "Construction of Fractal Objects with Iterated Function Systems," Computer Graphics, Vol. 19(3), pages 271-278, July, 1985, SIGGRAPH '85 Proceedings.
An IFS "attractor" is the set about which the random walk eventually clusters. The use of an IFS attractor to model a given object can provide significant data compression. However, this method is practical only if there exists a reasonably easy way to find the proper IFS to encode the object.
Informally, the object can be viewed as the settheoretic union of several sub-objects that are (smaller) copies of itself. The original object can be tiled with two or more sub-objects and the original object reproduced as long as the tiling scheme completely covers the original object, even if this means that two or more of the tiles overlap. If these conditions are met, an IFS can be determined or found whose attractor will be the original object. The accuracy of the resultant image is directly proportional to the exactness of the self-tiling process.
The self-tiling process of finding a proper IFS has been digitally automated with a simulated thermal annealing algorithm to adjust the parameters. The process starts with a rough tiling, and compares its initial tiled image with the object to be modeled. The measure of how well the tiled image matches the object is provided by computing the associated Hausdorff distances. The goal is to minimize the Hausdorff distance at each iteration. This process is repeated until a satisfactory match is achieved.
Thus, digital computation has been employed to perform contractive affine transformations of the original object and to compose a tiled image from a collection of these transformed images. The conventional digital process involves a great amount of computation on affine transformations and Hausdorff distances, and so it is slow.